#pragma once

/**********************************************************
oxsat - portable sat solver for windows and unix
Copyright (C) 2017  tj bandrowsky
Implementation of design by Bill Pugh.

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
*/

#include <functional>

namespace skip_lists
{

	const int BitsInRandom = 31;
	const int MaxNumberOfLevels = 20;
	const int MaxLevel = MaxNumberOfLevels - 1;

	class int_compare_type
	{
	public:
		inline static int compare(int a, int b)
		{
			return a - b;
		}
	};

	template <class KEY, class VALUE, class KEY_COMPARE> class skip_list_type
	{
	public:

		class node_type;
	
	protected:

		node_type *header;
		node_type *NIL;
		int randoms_left, random_bits, level;
		int count;
		KEY default_key;
		VALUE default_value;

	public:

		inline node_type *get_NIL() { return NIL;  }
		inline int size() { return count; }

		class node_type 
		{

		public:

			KEY			key;
			VALUE		value;
			int			nlevels;
			node_type	**forward;

			node_type() 
			{
			}

			node_type(int _nlevels, KEY _key, VALUE _value) :
				nlevels(_nlevels),
				key(_key),
				value(_value)
			{
				forward = new node_type*[nlevels + 1];
				for (int i = 0; i < nlevels; i++)
					forward[i] = nullptr;
			}
			node_type(int _nlevels, node_type *_NIL, KEY _key, VALUE _value)
				: 
				nlevels(_nlevels),
				key(_key), 
				value(_value)
			{
				forward = new node_type*[nlevels + 1];
				for (int i = 0; i < nlevels; i++)
					forward[i] = _NIL;
			}

			virtual ~node_type()
			{
				delete[] forward;
			}

			/*
			static void *operator new(size_t _size, int _num_levels)
			{
				char *t;

				size_t	node_size;
				node_size = _size + sizeof(node_type *) * (_num_levels + 1);

				t = new char[node_size];
				node_type *nt = reinterpret_cast<node_type *>(t);
				nt->num_levels = _num_levels;

				return reinterpret_cast<void *>(t);
			}

			static void operator delete(void *_t)
			{
				char *x = (char *)(_t);
				delete[] x;
			}
			*/
		};

		skip_list_type(KEY default_key, VALUE default_value) 
			: default_key(default_key),
			default_value(default_value)
		{
			level = 0;
			count = 0;
			random_bits = rand();
			randoms_left = BitsInRandom / 2;
			NIL = new node_type(0, default_key, default_value);
			header = new node_type(MaxNumberOfLevels, NIL, default_key, default_value);
		}

		virtual ~skip_list_type()
		{
			if (header != nullptr) 
			{
				clear();
				delete header;
				delete NIL;
			}
		}

		skip_list_type(const skip_list_type& _src)
		{
			level = 0;
			count = 0;
			random_bits = rand();
			randoms_left = BitsInRandom / 2;
			default_key = _src.default_key;
			default_value = _src.default_value;
			NIL = new node_type(0, default_key, default_value);
			header = new node_type(MaxNumberOfLevels, NIL, default_key, default_value);

			auto n = _src.first();
			while (n != nullptr) 
			{
				update(n->key, n->value);
				n = _src.next(n);
			}
		}

		skip_list_type(skip_list_type&& _src)
		{
			level = _src.level;
			count = _src.count;
			default_key = _src.default_key;
			default_value = _src.default_value;
			random_bits = _src.random_bits;
			randoms_left = _src.randoms_left;
			NIL = _src.NIL;
			header = _src.header;
			_src.NIL = nullptr;
			_src.header = nullptr;
			_src.count = 0;
		}

		void operator = (skip_list_type& _src)
		{
			default_key = _src.default_key;
			default_value = _src.default_value;

			clear();

			auto n = _src.first();
			while (n != nullptr)
			{
				update(n->key, n->value);
				n = _src.next(n);
			}
		}

		void operator = (skip_list_type&& _src)
		{
			if (this != &_src)
			{
				if (header != nullptr)
				{
					clear();
					delete header;
					delete NIL;
				}

				default_key = _src.default_key;
				default_value = _src.default_value;
				level = _src.level;
				count = _src.count;
				random_bits = _src.random_bits;
				randoms_left = _src.randoms_left;
				NIL = _src.NIL;
				header = _src.header;
				_src.NIL = nullptr;
				_src.header = nullptr;
				_src.count = 0;
			}
		}

		void clear()
		{
			if (header != nullptr && NIL != nullptr)
			{
				for (auto nt = first(); nt != nullptr; )
				{
					auto temp = next(nt);
					delete nt;
					nt = temp;
				}

				delete header;
				delete NIL;
				level = 0;
				count = 0;
				random_bits = rand();
				randoms_left = BitsInRandom / 2;
				NIL = new node_type(0, default_key, default_value);
				header = new node_type(MaxNumberOfLevels, NIL, default_key, default_value);
			}

		}

		int randomLevel()
		{
			int level = 0;
			int b;

			do {
				b = random_bits & 3;
				if (!b) level++;
				random_bits >>= 2;
				if (--randoms_left == 0) {
					random_bits = rand();
					randoms_left = BitsInRandom / 2;
				}
			} while (!b);

			return (level > MaxLevel ? MaxLevel : level);
		}

		// compare a node to a key for equality

		inline int compare(node_type *_node, KEY key)
		{
			if (_node != NIL) {
				return KEY_COMPARE::compare(_node->key, key);
			}
			else {
				return 1;
			}
		}

		node_type *update(KEY key, VALUE value)
		{
			int k;
			node_type *update[MaxNumberOfLevels];
			node_type *p, *q;

			p = header;
			k = level;

			do {
				while (q = p->forward[k], compare(q, key) < 0) {
					p = q;
				}
				update[k] = p;
			} while (--k >= 0);

			if (compare(q, key) == 0) 
			{
				q->value = value;
				return q;
			}

			k = randomLevel();
			if (k > level) {
				k = ++level;
				update[k] = header;
			};

			q = new node_type(k, NIL, key, value);

			if (q) {
				count++;

				do {
					p = update[k];
					q->forward[k] = p->forward[k];
					p->forward[k] = q;
				} while (--k >= 0);

				return q;

			}

			return NULL;
		}

		bool remove(KEY key)
		{
			int k, m;
			node_type *update[MaxNumberOfLevels];
			node_type *p, *q;

			p = header;
			k = m = level;

			do {
				while (q = p->forward[k], compare(q, key) < 0) {
					p = q;
				}
				update[k] = p;
			} while (--k >= 0);

			if (!compare(q, key)) {
				for (k = 0; k <= m && (p = update[k])->forward[k] == q; k++) {
					p->forward[k] = q->forward[k];
				}
				count--;
				while (header->forward[m] == NIL && m > 0) {
					m--;
				}
				level = m;
				delete q;
				return true;
			}
			else {
				return false;
			}
		}

		node_type *find(KEY key)
		{
#ifdef	TIME_SKIP_LIST
			benchmark::auto_timer_type methodtimer("skip_list_type::search");
#endif

			int k;
			node_type *p, *q = nullptr;
			p = header;
			k = level;
			do {
				while (q = p->forward[k], compare(q, key) < 0) {
					p = q;
				}
			} while (--k >= 0);
			if (compare(q, key)) {
				return nullptr;
			}
			return q;
		}

		template <class ENUMERATOR> void enumerate(int _id, ENUMERATOR enumerator)
		{
			node_type *q;

			// advance to the beginning of the list

			q = header->forward[0];

			while (q != NIL) 
			{
				enumerator(_id, q->key, q->value);
				q = q->forward[0]; // in a skip list, forward[0] of a node is a normal linked list!
			}
		}

		node_type *first() const
		{
			if (header->forward[0] != NIL)
				return header->forward[0];
			else
				return NULL;
		}

		node_type *next(node_type *_node) const
		{
			_node = _node->forward[0];
			if (_node && (_node != NIL)) {
				return _node;
			}
			return NULL;
		}

		bool remove_first()
		{
			bool result = false;
			node_type *q;

			q = header->forward[0];

			if (q != NIL) 
			{
				result = true;
				remove(q->key);
			}
			return result;
		}

	};

}